package com.zcmyth;

import java.util.Stack;

import com.google.common.base.Preconditions;

public class Words {

  private final String[] matrix;

  public Words(String[] matrix) {
    this.matrix = Preconditions.checkNotNull(matrix);
  }

  public void printAllWords() {
    if (matrix.length == 0 || matrix[0].length() == 0) {
      return;
    }
    int curX = 0, curY = 0;
    // true = right, false = down
    Stack<Boolean> stack = new Stack<Boolean>();
    print(stack);
    Boolean lastPop = null;
    while (true) {
      if (valid(curX + 1, curY) && lastPop == null) {
        stack.push(true);
        print(stack);
        curX++;
        lastPop = null;
      } else if (valid(curX, curY + 1) && !Boolean.FALSE.equals(lastPop)) {
        stack.push(false);
        print(stack);
        curY++;
        lastPop = null;
      } else {
        if (stack.isEmpty()) {
          break;
        }
        lastPop = stack.peek();
        if (stack.pop()) {
          curX--;
        } else {
          curY--;
        }
      }
    }
  }

  public int count(int x, int y) {
    if (!valid(x, y)) {
      return 0;
    }
    return count(x + 1, y) + count(x, y + 1) + 1;
  }

  private void print(Stack<Boolean> stack) {
    StringBuilder sb = new StringBuilder();
    sb.append(get(0, 0));
    int curX = 0, curY = 0;
    for (int i = 0; i < stack.size(); i++) {
      if (stack.get(i)) {
        curX++;
      } else {
        curY++;
      }
      sb.append(get(curX, curY));
    }
    System.out.println(sb.toString());
  }

  private Character get(int x, int y) {
    return this.matrix[x].charAt(y);
  }

  private boolean valid(int x, int y) {
    return matrix.length > x && matrix[x].length() > y;
  }

  public static void main(String[] args) {
    Words w = new Words(new String[] { "12", "34", "111" });
    w.printAllWords();
    System.out.println(w.count(0, 0));
  }

}
